#include <bits/stdc++.h>

using namespace std;
unordered_set<string> g_setResult; // 保存所有解
vector<char> g_vcInput = {'3', '3', '0', '0'};
unordered_map<char, int> g_mapInput;    // 不同字符的个数
unordered_map<char, int> g_mapUsed;     // 用掉的次数

// 判断是否需要收集解
bool NeedToCollect(int nId, const std::string& vnPath) {
    if (nId == 0) {
        return false;
    }
    if (g_setResult.count(vnPath) > 0) {
        return false;
    }
    return true;
}

// 收集解
void CollectResult(int nId, const string& vnPath) {
    g_setResult.insert(vnPath);
}

// 判断是否是死胡同
bool IsDeadNode(int nId, const string& vnPath) {
    return nId >= g_vcInput.size();
}

// 判断是否可行, 0为最高位
bool IsFeasible(int wei, char ch, const string& vnPath) {
    if ((wei == 0) && (ch == '0')) {
        return false;
    }
    if (g_mapUsed[ch] == g_mapInput[ch]) {
        return false;
    }
    return true;
}

// 获取下一个节点的ID
int GetNext(int nId) {
    return nId + 1;
}

void Select(string& vnPath, char ch) {
    vnPath.push_back(ch);
    g_mapUsed[ch]++;
}

void Unselect(string& vnPath, char ch) {
    vnPath.pop_back();
    g_mapUsed[ch]--;
}

// 回溯算法框架
void Backtrack(int nId, const std::vector<char>& vnRange, std::string& vnPath) {
    if (NeedToCollect(nId, vnPath)) {
        CollectResult(nId, vnPath);
    }

    if (IsDeadNode(nId, vnPath)) {
        return;
    }

    for (int ch : vnRange) {
        if (!IsFeasible(nId, ch, vnPath)) {
            continue;
        }

        Select(vnPath, ch);   // 选择当前列
        Backtrack(GetNext(nId), vnRange, vnPath);
        Unselect(vnPath, ch); // 撤销选择
    }
}

// 打印解
void PrintResult(const std::unordered_set<string>& results) {
    std::cout << "Total solutions: " << results.size() << std::endl;    for (const auto& solution : results) {
        std::cout << solution;
        std::cout << std::endl;
    }
}

int main() {
    std::string vnPath;
    for (auto ch : g_vcInput) {
        g_mapInput[ch]++;
        if (ch == '0') {
            g_setResult.insert("0");
        }
    }
    Backtrack(0, g_vcInput, vnPath);
    PrintResult(g_setResult);
    return 0;
}